// 也称为“寻找循环的入口点”， 目的是给定一个可能包含环的链表，找出环的入口节点。如果链表中没有环，则返回 null。

// 思路： 分两个阶段，第一，是否有环，这个和环形链表1思路一致，第二，通过数学公式可以证明，从head到入环带点，和从相遇点到入环点的距离相等
// 时间复杂度：O(n)，n是链表的节点数
// 空间复杂度：O(1)

const { LinkedList, ListNode} = require('./64.设计链表')
function detectCycle(head) {
    if (!head || !head.next) {
        return null
    }
    let slow = head.next
    let fast = head.next.next
    while (slow !== fast) {
        if (!fast || !fast.next) {
            return null
        }
        slow = slow.next
        fast = fast.next.next
    }
    // 此时找到相遇点slow
    let cur1 = head
    while (cur1 !== slow) {
        cur1 = cur1.next
        slow = slow.next
    }
    return slow
}

let node0 = new ListNode('abin')
let node1 = new ListNode(2)
let node2 = new ListNode(5)
let node3 = new ListNode(1)
let node4 = new ListNode(7)
node0.next = node1
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node1

console.log(detectCycle(node0))